#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <deque>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() < t.size()) return "";

        unordered_map<char, int> exp;
        for (auto e : t) exp[e]++;

        int begin = 0, len = 0x3f3f3f3f;
        int have = 0, tcount = exp.size();
        unordered_map<char, int> hash;
        for (int i = 0, j = 0; i < s.size(); ++i) {
            if (exp.find(s[i]) != exp.end()) {
                hash[s[i]]++;
                if (exp[s[i]] == hash[s[i]]) {
                    have++;
                }
            }
            while (have == tcount) {
                if (len > i - j + 1) {
                    len = i - j + 1;
                    begin = j;
                }
                if (exp.find(s[j]) != exp.end()) {
                    hash[s[j]]--;
                    if (hash[s[j]] < exp[s[j]]) have--;
                }
                j++;
            }
        }

        return len == 0x3f3f3f3f ? "" : s.substr(begin, len);
    }
};

int main()
{
    cout << Solution().minWindow("ADOBECODEBANC", "ABC");

    return 0;
}